#include <malloc.h>
#include <stdio.h>

typedef struct Node {
    int first;
    int second;
    struct Node *next;
} Node;

typedef struct {
    Node *stack;
    int idx;
} StockSpanner;

Node* nodeCreate(int first, int second) {
    Node *obj = (Node *)malloc(sizeof(Node));
    obj->first = first;
    obj->second = second;
    obj->next = NULL;
    return obj;
}

StockSpanner* stockSpannerCreate() {
    StockSpanner *obj = (StockSpanner *)malloc(sizeof(StockSpanner));
    obj->idx = -1;
    obj->stack = nodeCreate(-1, INT_MAX);
    return obj;
}

int stockSpannerNext(StockSpanner* obj, int price) {
    obj->idx++;
    while (price >= obj->stack->second) {
        Node *p = obj->stack;
        obj->stack = obj->stack->next;
        free(p);
    }
    int ret  = obj->idx - obj->stack->first;
    Node *p = nodeCreate(obj->idx, price);
    p->next = obj->stack;
    obj->stack = p;
    return ret;
}

void stockSpannerFree(StockSpanner* obj) {
    for (Node *p = obj->stack; p;) {
        Node *node = p;
        p = p->next;
        free(node);
    }
    free(obj);
}

int main()
{
//    ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
//    [[], [100], [80], [60], [70], [60], [75], [85]]
    StockSpanner *obj = stockSpannerCreate();
    printf("%d ", stockSpannerNext(obj, 100));
    printf("%d ", stockSpannerNext(obj, 80));
    printf("%d ", stockSpannerNext(obj, 60));
    printf("%d ", stockSpannerNext(obj, 70));
    printf("%d ", stockSpannerNext(obj, 60));
    printf("%d ", stockSpannerNext(obj, 75));
    printf("%d ", stockSpannerNext(obj, 85));
    stockSpannerFree(obj);
}

